Wir haben uns jetzt angefangen mit einer neuen Klasse von Problemen zu beschäftigen,

nämlich solchen Problemen, die sich deren Zustand durch im Wesentlichen Features beschreiben lässt.

Also beschreiben lässt durch Zustände einzelner Koordinaten kann man sagen.

Das heißt wir haben die Zustände nicht mehr Black Box, sondern beschrieben durch einen Vektor von Variablen, die alle Werte kriegen können.

Es gibt dabei, wir hatten uns angeguckt den Fußballkalender, wir hatten uns angeguckt Sudoku, da ist das besonders deutlich.

Wir haben 81 Features für jede Zelle 1 und wir haben in jedem einen Wert.

Die Lösung ist gerade so, dass jeder Zelle einen Wert bekommt und zwischendurch haben wir Zustände, wo nur Teile der ganzen Sache einen Wert haben.

Landkarten einfärben ist eine andere Sache. Wir haben hier 7 Territorien, die sollen alle einen Wert, also eine Farbe bekommen.

Das interessante dabei sind die sogenannten Constraints, die Nebenbedingungen, die zu erfüllen sind.

Hier zum Beispiel, dass keine zwei benachbarten Länder die gleiche Farbe haben.

Bei der Bundesliga gibt es eine größere Menge an Constraints.

Wir haben die Situation, dass dadurch, dass wir in den Zuständen mehr Struktur haben, können wir bessere Heuristiken bauen,

können wir also wesentlich bessere Laufzeiten erreichen als irgendwelche Brute Force Algorithmen, die man sich sonst so ausdenkt.

Es gibt eine ganze Menge Solver, die man einfach runterladen kann, die sind mittlerweile sehr gut.

Zum Beispiel Minion ist einer, ich weiß nicht, werden wir da Übungsaufgaben zumachen? Bitte, Minion?

Ich denke, das ist ganz gut, wenn wir Ihnen mal tatsächlich größere CSP-Eddinger geben, die Sie dann selber modellieren und dann irgendwie so etwas wie Minion drauf laufen lassen.

Wir haben uns Probleme angeguckt, die man durch Constraints Satisfaction lösen kann.

Und waren dann so langsam die Mathematik der ganzen Sache eingestiegen.

Wir werden heute eben Suchalgorithmen angucken mit relativ einfachen Heuristiken, die schon eine ganze Menge bringen.

Dann hatten wir uns eine Anwendung für Constraints Satisfaction Techniken angeguckt, die erste im Wesentlichen,

wo es darum ging, solche Bleistiftzeichnungen als 3D-Objekte zu verstehen,

insbesondere zu verstehen, ob irgendwelche Ecken konkaff oder konvex sind, das ist sozusagen die Verständnisleistung daran.

Und waren dann darauf gekommen, dass man die labeln kann, jede Ecke, von denen es genau 18 gibt, das sind unsere endlichen Domänen, jede Ecke hier, jede Verbindung ist wiederum eine Variable,

die kriegt einen Wert aus diesen 18 und die Constraints sind immer, wenn es eine Verbindung zwischen zwei Ecken gibt, wie zum Beispiel hier, müssen die Kantenlabels gleich sein.

Einfaches Constraints Satisfaction Problem.

Man kann sich vorstellen, dass schon bei einer so einfachen, relativ kleinen Dinge, mit 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 zähle ich jetzt mal, vielleicht 12, ich weiß nicht, ob ich das schon hatte,

haben wir natürlich 12 auf 18 Möglichkeiten und wenn man die alle durchprobieren will, dann ist man auch eine Weile lang beschäftigt.

Und man kann mit dieser Sache, wenn man Constraints Satisfaction Algorithmen macht, so wie wir sie jetzt hier kennenlernen wollen,

kann man die sehr schnell lösen und kann dann auch relativ komplexe Objekte verstehen und wir hatten uns auch einige angeguckt, die nicht zu verstehen sind,

weil sie zum Beispiel dieses hier keine Kantenlabels haben und es gibt auch Objekte, bei denen diese ganze Analyse tatsächlich fehlschlägt.

Als Mensch hat man hier Schwierigkeiten, ob man das tatsächlich aus dem Holzblock aussägen könnte und der Woltz-Algorithmus hat auch Schwierigkeiten.

Dieses Ding hat ein Labeling, was konsistent ist, aber es gibt, wie Sie sehr gut wissen, kein 3D-Objekt, was tatsächlich dem entspricht.

Genau, wir hatten dann angefangen, uns Gedanken darüber zu machen, wie man CSPs löst und haben uns so mal wieder typisch vorgetastet,

die Fragen gestellt, kann ich mich auf diskrete Variablen beschränken, was passiert, wenn ich unendliche Domains habe, was passiert, wenn ich kontinuierliche Variablen habe.

Es stellt sich heraus, dass man alle diese Sachen mit Vorsicht genießen muss, denn sie machen die Sache sehr viel schwieriger, als man das für KI1 behandeln wird.

Wie eigentlich immer sind wir in der KI1 auch zwei auf einem Gang durch den Gemüsegarten, wo man zwar an jedem Pflänzchen einmal riecht und schmeckt,

aber nirgendswo so richtig tief einsteigt. Jedes von diesen Themen ist so, dass da aktiv Forschung gemacht wird und auch noch aktiv Fortschritte gemacht werden.

Wir hatten uns Constraints angeguckt, einschnellige Constraints, zum Beispiel könnte man hier sagen sowas wie South Africa darf nicht grün, nicht South Africa,

ich komme immer wieder auf die falsche Fährte hier, Southern Australia, falscher Kontinent, diese darf nicht grün sein,

Binaire Constraints, Southern Australia und Western Australia, Grenzen aneinander dürfen also nicht dieselbe Farbe kriegen.

Dann gibt es noch etwas, was wir Higher Order Constraints nennen, die also zwischen drei oder mehr Dingen sind.

Die gibt es bei der Karte nicht, aber wir haben uns dann hinterher als letztes dieses Send More Money angeguckt und da haben wir ziemlich wüste Constraints.

Eine mit 1, 2, 3, 4, 5, 6, 7, 8 und die anderen sind glaube ich alle schon vorgekommen, ne, 9, also neuner Constraints.

Soweit waren wir gekommen, gibt es hier irgendwo ein Fragen? Gut, dann würde ich jetzt noch mal Dennis bitten uns ein paar Worte zu dem Calaturnier zu sagen.

Um das Framework hier, du brauchtest einen, welche? Und dann?

Ja, also wir wissen ja primitiv hier, worum es geht, das Ziel ist es einen Calat-Agenten zu implementieren.

Parameter sind folgendermachen, ihr habt Zeit das Ganze abzugeben, hier ein übliches Bibusblatt bis zum 10.12., also übernächsten Sonntag.

Glaub ich? Genau, bis übernächsten Sonntag, die Idee ist, wenn ihr es überhaupt schafft eine funktionierende Calat-Agenten zu implementieren, das ist einfach Teil der üblichen Hausaufgabe,

da gibt es 100 Punkte drauf, wenn es funktioniert, funktioniert und besser spielt als random. Ich habe auch einen Agenten implementiert, der macht es dann über Zufall,

irgendwas zu ziehen, also wenn ich da auch die Luft geht und die Luft gegeneinander antreten lasse und es stellt sich heraus, dass irgendwer konsistent schlechter ist als zu anderen, dann gibt es halt Punkteabzug, aber prinzipiell, wenn ihr eine KI abgibt, sollte das nicht passieren.